package main

func minFallingPathSum(matrix [][]int) int {
	dp := make([][]int, len(matrix))
	for i := range dp {
		dp[i] = make([]int, len(matrix))
	}
	for i, row := range matrix {
		for j := range row {
			if i == 0 {
				dp[i][j] = matrix[i][j]
			} else {
				min := dp[i-1][j]
				if j-1 >= 0 && dp[i-1][j-1] < min {
					min = dp[i-1][j-1]
				}
				if j+1 < len(row) && dp[i-1][j+1] < min {
					min = dp[i-1][j+1]
				}
				dp[i][j] = min + matrix[i][j]
			}
		}
	}
	min := 1 << 31
	for _, v := range dp[len(dp)-1] {
		if v < min {
			min = v
		}
	}
	return min
}

func main() {
	// m := [][]int{
	// 	{2, 1, 3},
	// 	{6, 5, 4},
	// 	{7, 8, 9},
	// }
	m := [][]int{
		{17, 82},
		{1, -44},
	}
	res := minFallingPathSum(m)
	println(res)
}
